﻿#pragma once

#include "baseFunc.hpp"

/*
 给定字符串J 代表石头中宝石的类型，和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型，
 你想知道你拥有的石头中有多少是宝石。
 J 中的字母不重复，J 和 S中的所有字符都是字母。字母区分大小写，因此"a"和"A"是不同类型的石头。
示例 1:
输入: J = "aA", S = "aAAbbbb"
输出: 3
示例 2:
输入: J = "z", S = "ZZ"
输出: 0
*/
int numJewelsInStones(string J, string S) {
	int nCount = 0;
	map<char, int> tempMap;
	// 
	for (int i = 0; i < J.length(); i++)
	{
		tempMap.insert(make_pair(J[i],0));
	}
	for (int i = 0; i < S.length(); i++)
	{
		if (tempMap.find(S[i]) != tempMap.end())
		{
			nCount++;
		}
	}
	return nCount;
}


/* 
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例 :
给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回[0, 1]
*/
vector<int> twoSum(vector<int>& nums, int target) {
	map<int, int> temp;
	int t = target;
	vector<int> dest;
	for (int i = 0; i < nums.size(); i++)
	{
		t = target - nums[i];
		if (temp.find(t) != temp.end())
		{
			dest.push_back(temp[t]);
			dest.push_back(i);
			return dest;
		}
		temp.insert(make_pair(nums[i], i));
	}
	return dest;
}

/*
实现函数 ToLowerCase()，该函数接收一个字符串参数 str，并将该字符串中的大写字母转换成小写字母，之后返回新的字符串。

示例 1：
输入: "Hello"
输出: "hello"
示例 2：
输入: "here"
输出: "here"
示例 3：
输入: "LOVELY"
输出: "lovely"
*/
string toLowerCase(string str) {
	//int n = 'A' - 'a';
	int len = str.length();
	for (int i=0; i<len; i++)
	{
		if (str[i] >= 'A' && str[i] <= 'Z') {
			str[i] = str[i]- 'A' + 'a';
		}
	}
	return str;
}

/*
示例 1:
输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:
输入: head = [4,5,1,9], node = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

说明:
链表至少包含两个节点。
链表中所有节点的值都是唯一的。
给定的节点为非末尾节点并且一定是链表中的一个有效节点。
不要从你的函数中返回任何结果。
*/
void deleteNode(ListNode* node) {
	node->val = node->next->val;
	node->next = node->next->next;
}


/*
给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

示例 1：
输入：[-4,-1,0,3,10]
输出：[0,1,9,16,100]
示例 2：
输入：[-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：
1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A 已按非递减顺序排序。
*/
vector<int> sortedSquares(vector<int>& A) {
	vector<int> temp;
	for (int i = 0, j = A.size() - 1; i <= j; )
	{
		if (abs(A[i]) < abs(A[j]))
		{
			temp.push_back(A[j]);
			j--;
		}
		else
		{
			temp.push_back(A[i]);
			i++;
		}
	}
	// 
	vector<int> result;
	for (int i = temp.size()-1; i >= 0; i--)
	{
		result.push_back(temp[i] * temp[i]);
	}
	
	return result;
}


/*
给定一个二进制矩阵 A，我们想先水平翻转图像，然后反转图像并返回结果。
水平翻转图片就是将图片的每一行都进行翻转，即逆序。例如，水平翻转 [1, 1, 0] 的结果是 [0, 1, 1]。
反转图片的意思是图片中的 0 全部被 1 替换， 1 全部被 0 替换。例如，反转 [0, 1, 1] 的结果是 [1, 0, 0]。
示例 1:
输入: [[1,1,0],[1,0,1],[0,0,0]]
输出: [[1,0,0],[0,1,0],[1,1,1]]
解释: 首先翻转每一行: [[0,1,1],[1,0,1],[0,0,0]]；
	 然后反转图片: [[1,0,0],[0,1,0],[1,1,1]]
示例 2:
输入: [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
输出: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
解释: 首先翻转每一行: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]]；
	 然后反转图片: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
*/
vector<vector<int>> flipAndInvertImage(vector<vector<int>>& A) {
	int n,len;
	for (int i = 0; i < A.size(); i++)
	{
		len = A[i].size()/2;
		for (int j = 0; j < len; j++)
		{
			n = A[i][j];
			A[i][j] = A[i][A[i].size()-j-1];
			A[i][A[i].size() - j - 1] = n;
		}
	}
	for (int i = 0; i < A.size(); i++)
	{
		for (int j = 0; j < A[i].size(); j++)
		{
			A[i][j] = !A[i][j];
		}
	}
	return A;
}


/*
国际摩尔斯密码定义一种标准编码方式，将每个字母对应于一个由一系列点和短线组成的字符串， 比如: "a" 对应 ".-", "b" 对应 "-...", "c" 对应 "-.-.", 等等。
为了方便，所有26个英文字母对应摩尔斯密码表如下：
[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
给定一个单词列表，每个单词可以写成每个字母对应摩尔斯密码的组合。例如，"cab" 可以写成 "-.-..--..."，(即 "-.-." + "-..." + ".-"字符串的结合)。我们将这样一个连接过程称作单词翻译。
返回我们可以获得所有词不同单词翻译的数量。
例如:
输入: words = ["gin", "zen", "gig", "msg"]
输出: 2
解释:
各单词翻译如下:
"gin" -> "--...-."
"zen" -> "--...-."
"gig" -> "--...--."
"msg" -> "--...--."

共有 2 种不同翻译, "--...-." 和 "--...--.".
*/
int uniqueMorseRepresentations(vector<string>& words) {
	string tables[] = {
		".-","-...","-.-.","-..",".","..-.","--.",// abcdefg
		"....","..",".---","-.-",".-..","--","-.",// hijklmn
		"---",".--.","--.-",".-.","...","-",      // opqrst
		"..-","...-",".--","-..-","-.--","--.."   // uvwxyz
	};
	map<string, string>tempMap;
	string temp;
	for (int i = 0; i < words.size(); i++)
	{
		temp = "";
		for (int j = 0; j < words[i].length(); j++)
		{
			temp += tables[words[i][j]-'a'];
		}
		tempMap.insert(make_pair(temp,words[i]));
	}
	return tempMap.size();
}

/*
给定只含 "I"（增大）或 "D"（减小）的字符串 S ，令 N = S.length。
返回 [0, 1, ..., N] 的任意排列 A 使得对于所有 i = 0, ..., N-1，都有：
如果 S[i] == "I"，那么 A[i] < A[i+1]
如果 S[i] == "D"，那么 A[i] > A[i+1]

示例 1：
输出："IDID"
输出：[0,4,1,3,2]
示例 2：
输出："III"
输出：[0,1,2,3]
示例 3：
输出："DDI"
输出：[3,2,0,1]
*/
vector<int> diStringMatch(string S) {
	vector<int> temp;
	return temp;
}


/*
在二维平面上，有一个机器人从原点 (0, 0) 开始。给出它的移动顺序，判断这个机器人在完成移动后是否在 (0, 0) 处结束。
移动顺序由字符串表示。字符 move[i] 表示其第 i 次移动。机器人的有效动作有 R（右），L（左），U（上）和 D（下）。如果机器人在完成所有动作后返回原点，则返回 true。否则，返回 false。
注意：机器人“面朝”的方向无关紧要。 “R” 将始终使机器人向右移动一次，“L” 将始终向左移动等。此外，假设每次移动机器人的移动幅度相同。

示例 1:
输入: "UD"
输出: true
解释：机器人向上移动一次，然后向下移动一次。所有动作都具有相同的幅度，因此它最终回到它开始的原点。因此，我们返回 true。
示例 2:
输入: "LL"
输出: false
解释：机器人向左移动两次。它最终位于原点的左侧，距原点有两次 “移动” 的距离。我们返回 false，因为它在移动结束时没有返回原点。
*/
bool judgeCircle(string moves) {
	
	int nCount1 = 0;
	int nCount2 = 0;
	for (int i = 0; i < moves.length(); i++)
	{
		if (moves[i] == 'U')
		{
			nCount1++;
		}
		else if (moves[i] == 'D')
		{
			nCount1--;
		}
		else if (moves[i] == 'L')
		{
			nCount2--;
		}
		else if (moves[i] == 'R')
		{
			nCount2++;
		}
	}
	return nCount1 == 0 && nCount2 == 0;
}


/*
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
示例 1:
输入:
	Tree 1                     Tree 2
		  1                         2
		 / \                       / \
		3   2                     1   3
	   /                           \   \
	  5                             4   7
输出:
合并后的树:
		 3
		/ \
	   4   5
	  / \   \
	 5   4   7
注意: 合并必须从两个树的根节点开始。
 */
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
	if (t1 == NULL)
	{
		t1 = t2;
		return t2;
	}
	else if (t2 == NULL)
	{
		return t1;
	}
	else
	{
		t1->val += t2->val;
		t1->left = mergeTrees(t1->left, t2->left);
		t1->right = mergeTrees(t1->right, t2->right);
	}
	return t1;
}


/*
两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给出两个整数 x 和 y，计算它们之间的汉明距离。
注意：
0 ≤ x, y < 231.
示例:
输入: x = 1, y = 4

输出: 2

解释:
1   (0 0 0 1)
4   (0 1 0 0)
	   ↑   ↑

上面的箭头指出了对应二进制位不同的位置。
*/
int hammingDistance(int x, int y) {
	int nCount = x ^ y;
	int yu = 0;
	while (nCount > 0)
	{
		yu += (nCount % 2);
		nCount /= 2;
	}
	return yu;
}

/*
给定一个非负整数数组 A，返回一个由 A 的所有偶数元素组成的数组，后面跟 A 的所有奇数元素。
你可以返回满足此条件的任何数组作为答案。

示例：
输入：[3,1,2,4]
输出：[2,4,3,1]
输出 [4,2,3,1]，[2,4,1,3] 和 [4,2,1,3] 也会被接受。

提示：
1 <= A.length <= 5000
0 <= A[i] <= 5000
*/
vector<int> sortArrayByParity(vector<int>& A) {
	vector<int> retDan;
	vector<int> retShuang;
	for (int i = 0; i < A.size(); i++)
	{
		if (A[i] % 2 == 1) 
		{
			retDan.push_back(A[i]);
		}
		else
		{
			retShuang.push_back(A[i]);
		}
	}
	retShuang.insert(retShuang.end(),retDan.begin(),retDan.end());
	return retShuang;
}
vector<int> sortArrayByParity2(vector<int>& A) {
	int AI = 0;
	int AJ = 0;
	for (int i = 0, j=A.size()-1; i < j;)
	{
		AI = A[i] % 2;
		AJ = A[j] % 2;
		if (AI && !AJ)
		{
			int temp = A[i];
			A[i] = A[j];
			A[j] = temp;
		}
		else if (!AI) 
		{
			i++;
		}
		else if (AJ)
		{
			j--;
		}
	}
	return A;
}

/*
翻转一棵二叉树。
示例：
输入：
	 4
   /   \
  2     7
 / \   / \
1   3 6   9
输出：
	 4
   /   \
  7     2
 / \   / \
9   6 3   1
*/
TreeNode* invertTree(TreeNode* root) {
	if (root == NULL) return NULL;
	if (root->left == NULL && root->right == NULL) return root;
	TreeNode *temp = invertTree(root->right);
	root->right = invertTree(root->left);
	root->left = temp;
	return root;
}

/*

*/
int removeDuplicates(vector<int>& A)
{
	int i = 0;
	int j = 0;
	int k = 0;
	int t = 0;
	int len = A.size();
	for (i = 0, j=1; i < len - 1 && j < len; )
	{
		if (A[i] == A[j])
		{
			j++;
		}
		else 
		{
			if (j - i >= 2)
			{
				for (k = i + 2,t=j; t < A.size(); k++,t++)
				{
					A[k] = A[t];
				}
				len = len - (t-k);
				i = i + 2;
			}
			else
			{
				i = j;
			}
			j = i + 1;
		}
		//cout << "i,j = " << i << " " << j << endl;
	}

	if (len-i > 2)
	{
		len = i + 2;
	}

	return len;
	//cout << nCount << endl;
}


/*
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
*/
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
	if (l1 == NULL && l2 == NULL) return NULL;

	ListNode* pHead = NULL;
	// 计算结果
	while (l1 != NULL || l2 != NULL)
	{
		l1->val += l2->val;
		//temp.push_back(l1->val + l2->val);
		l1 = l1->next;
		l2 = l2->next;
	}

	return pHead;
}


/*
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:
	可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
	你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
*/
/*
思路：用数组记录从开头到当前的最长上升序列，每次加上一个
*/
int lengthOfLIS(vector<int>& nums) {
	if (nums.size() == 0) return 0;
	if (nums.size() == 1) return 1;
	int nMaxCount = 1;

	vector<int> num;
	for (int i = 0; i < nums.size(); i++)
	{
		num.push_back(1);
		for (int j = 0; j < i; j++)
		{
			if (nums[j]<nums[i] && num[j] + 1>num[i])
				num[i] = num[j] + 1;
		}
	}
	for (int i = 0; i < num.size(); i++)
	{
		if (nMaxCount < num[i])
		{
			nMaxCount = num[i];
		}
	}
	return nMaxCount;
}


/*
给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
在杨辉三角中，每个数是它左上方和右上方的数的和。
示例:
输入: 5
输出:
[
	 [1],
	[1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]
*/
vector<vector<int>> generate(int numRows) {
	vector<vector<int>> vec;
	for (int i = 0; i < numRows; i++)
	{
		vector<int> tempVec;
		for (int j = 0; j <= i; j++)
		{
			if (j == 0 || j == i)
			{
				tempVec.push_back(1);
			}
			else
			{
				tempVec.push_back(vec[i-1][j-1]+vec[i-1][j]);
			}
		}
		vec.push_back(tempVec);
	}
	return vec;
}
/*
返回杨辉三角的第K行
*/
vector<int> getRow(int rowIndex) {
	vector<int> vec;
	vector<int> vecLast;
	int nIndex = 0;
	int temp = 0;
	for (int i = 0; i<rowIndex; i++)
	{
		vec.clear();
		temp = nIndex - i;
		for (int j = 0; j <= i; j++, nIndex++)
		{
			if (j == 0 || j == i)
			{
				vec.push_back(1);
			}
			else
			{
				vec.push_back(vecLast[j - 1] + vecLast[j]);
			}
		}
		vecLast = vec;
	}
	return vec;
}

/*
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
*/
ListNode* reverseList(ListNode* head) {
	if (head == NULL || head->next == NULL)
		return head;
	ListNode* pHead = head;
	ListNode* pTemp = head->next;
	ListNode* pNext = NULL;
	while (pTemp != NULL)
	{
		//pTemp = head->next;
		pNext = pTemp->next;
		pTemp->next = head;
		head = pTemp;
		pTemp = pTemp->next;
	}
	pHead->next = NULL;
	return head;
}


/*
给定二叉搜索树的根结点 root，返回 L 和 R（含）之间的所有结点的值的和。
二叉搜索树保证具有唯一的值。
示例 1：
输入：root = [10,5,15,3,7,null,18], L = 7, R = 15
输出：32
示例 2：
输入：root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
输出：23
提示：
	树中的结点数量最多为 10000 个。
	最终的答案保证小于 2^31。
*/
int rangeSumBST(TreeNode* root, int L, int R) {
	int nCount = 0;
	return nCount;
}


/*
有效括号字符串为空 ("")、"(" + A + ")" 或 A + B，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。例如，""，"()"，"(())()" 和 "(()(()))" 都是有效的括号字符串。

如果有效字符串 S 非空，且不存在将其拆分为 S = A+B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。

给出一个非空有效字符串 S，考虑将其进行原语化分解，使得：S = P_1 + P_2 + ... + P_k，其中 P_i 是有效括号字符串原语。

对 S 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 S 。

示例 1：

输入："(()())(())"
输出："()()()"
解释：
输入字符串为 "(()())(())"，原语化分解得到 "(()())" + "(())"，
删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。

示例 2：

输入："(()())(())(()(()))"
输出："()()()()(())"
解释：
输入字符串为 "(()())(())(()(()))"，原语化分解得到 "(()())" + "(())" + "(()(()))"，
删除每隔部分中的最外层括号后得到 "()()" + "()" + "()(())" = "()()()()(())"。

示例 3：

输入："()()"
输出：""
解释：
输入字符串为 "()()"，原语化分解得到 "()" + "()"，
删除每个部分中的最外层括号后得到 "" + "" = ""。
*/
// 逐个查找(，与之对应的)
string removeOuterParentheses(string S) {
	string ret = "";
	int nCount = 0;
	for (int i = 0; i < S.length(); i++)
	{
		if (nCount == 0)
		{
			if (S[i] == '(')
			{
				nCount++;
			}
			else
			{
			}
		}
		else
		{
			if (S[i] == '(')
			{
				nCount++;
				ret += S[i];
			}
			else
			{
				nCount--;
				if (nCount != 0)
				{
					ret += S[i];
				}
			}
		}
	}
	return ret;
}


/*
你和你的朋友，两个人一起玩 Nim 游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。
你们是聪明人，每一步都是最优解。 编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。
示例:
输入: 4
输出: false
解释: 如果堆中有 4 块石头，那么你永远不会赢得比赛；
	 因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。
*/
bool canWinNim(int n) {
	if (n % 4 == 0)return false;
	return true;
}


/*
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
*/
void reverseString(vector<char>& s) {
	char ch;
	int len = s.size();
	for (int i = 0; i < len / 2; i++)
	{
		swap(s[i], s[len - i - 1]);
	}
}


/*
给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
示例 1:
输入: "Let's take LeetCode contest"
输出: "s'teL ekat edoCteeL tsetnoc"
注意：在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。
*/
string reverseWords(string s) {
	int len = s.length();
	if (len < 1) return s;
	if (s[len - 1] != ' ') len++;
	int nIndex = 0;
	char ch;
	for (int i = 0; i < len; i++)
	{
		if (s[i] == ' ' || i==len-1)
		{
			//if (i == len - 1 && s[i] != ' ') nIndex++;
			for (int j = 0; j < nIndex / 2; j++)
			{
				ch = s[i - j - 1];
				s[i - j - 1] = s[i - nIndex + j];
				s[i - nIndex + j] = ch;
			}
			nIndex = 0;
		}
		else
		{
			nIndex++;
		}
	}
	return s;
}


/*
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
*/
int singleNumber(vector<int>& nums) {
	int nRet = 0;
	for (int i = 0; i < nums.size(); i++)
	{
		nRet ^= nums[i];
	}
	return nRet;
}

/*
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2
*/
int majorityElement(vector<int>& nums) {
	if (nums.size() < 1) return 0;
	int nCount = 1;
	int ret = nums[0];
	for (int i = 1; i < nums.size(); i++)
	{
		if (ret != nums[i])
		{
			nCount--;
			if (nCount == 0)
			{
				ret = nums[i];
			}
		}
		else
		{
			nCount++;
		}
	}
	return ret;
}

/*
自除数 是指可以被它包含的每一位数除尽的数。
例如，128 是一个自除数，因为 128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。
还有，自除数不允许包含 0 。
给定上边界和下边界数字，输出一个列表，列表的元素是边界（含边界）内所有的自除数。
示例 1：
输入：
上边界left = 1, 下边界right = 22
输出： [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]
注意：
	每个输入参数的边界满足 1 <= left <= right <= 10000。
*/
bool bSelf(int n)
{
	int nYu;
	int nTemp = n;
	while (nTemp)
	{
		nYu = nTemp % 10;
		if (nYu == 0 || n % nYu != 0)
		{
			return false;
		}
		nTemp /= 10;
	}
	return true;
}
vector<int> selfDividingNumbers(int left, int right) {
	vector<int> vec;
	for (int i = left; i <= right; i++)
	{
		if (bSelf(i)) 
		{
			vec.push_back(i);
		}
	}
	return vec;
}


/*
我们把符合下列属性的数组 A 称作山脉：
	A.length >= 3
	存在 0 < i < A.length - 1 使得A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]
给定一个确定为山脉的数组，返回任何满足 A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1] 的 i 的值。
示例 1：
输入：[0,1,0]
输出：1
示例 2：
输入：[0,2,1,0]
输出：1
提示：
	3 <= A.length <= 10000
	0 <= A[i] <= 10^6
	A 是如上定义的山脉
*/
int peakIndexInMountainArray(vector<int>& A) {
	int i = 0;
	for (; i < A.size()-1; i++)
	{
		if (A[i] > A[i - 1])break;
	}
	return i;
}


/*
给定一个正整数，输出它的补数。补数是对该数的二进制表示取反。
注意:
	给定的整数保证在32位带符号整数的范围内。
	你可以假定二进制数不包含前导零位。
示例 1:
输入: 5
输出: 2
解释: 5的二进制表示为101（没有前导零位），其补数为010。所以你需要输出2。
示例 2:
输入: 1
输出: 0
解释: 1的二进制表示为1（没有前导零位），其补数为0。所以你需要输出0。
*/
int findComplement(int num) {
	return num;
}
